
{\chapter{Definitions}}

\begin{eqnarray*}
T(n) \ = \ O(g(n))  & \Longleftrightarrow  &
     {\mathit{there\ exists}} \ g(n), \, n_0 \ge 0, \, c > 0
     \ {\mathit{such\ that}} \\
&  & T(n) \ \le \ c{\cdot}g(n)
     \ {\mathit{for\ all}} \ n > n_0 \\
&  & \\
T(n) \ = \ \Omega(g(n))  & \Longleftrightarrow  &
     {\mathit{there\ exists}} \ g(n), \, n_0 \ge 0, \, c > 0
     \ {\mathit{such\ that}} \\
&  & T(n) \ \ge \ c{\cdot}g(n)
     \ {\mathit{for\ all}} \ n > n_0 \\
&  & \\
T(n) \ = \ \Theta(g(n))  & \Longleftrightarrow  &
     T(n) \, = \, O(g(n)) \ {\mathit{and}} \ T(n) \, = \, \Omega(g(n)) \\
&  & \\
T(n) \ = \ o(g(n))  & \Longleftrightarrow  &
     {\mathit{there\ exists}} \ g(n), \, n_0 \ge 0, \, c > 0
     \ {\mathit{such\ that}} \\
&  & T(n) \ < \ c{\cdot}g(n)
     \ {\mathit{for\ all}} \ n > n_0 \\
&  & \\
T(n) \ = \ \omega(g(n))  & \Longleftrightarrow  &
     {\mathit{there\ exists}} \ g(n), \, n_0 \ge 0, \, c > 0
     \ {\mathit{such\ that}} \\
&  & T(n) \ > \ c{\cdot}g(n)
     \ {\mathit{for\ all}} \ n > n_0 \\
\end{eqnarray*}

